package a_doubleWrite;

import util.TreeNode;

import java.util.*;

/**
 * 打家劫舍 III,不能使用层次遍历相加，因为可能不是在同一层
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-07-31 11:47
 */
public class L337 {
    /*超时
    public int rob(TreeNode root) {
        if(root==null) return 0;
        int money=root.val;
        if(root.left!=null){
            money+=rob(root.left.left)+rob(root.left.right);
        }
        if(root.right!=null){
            money+=rob(root.right.left)+rob(root.right.right);
        }
        return Math.max(money, rob(root.left)+rob(root.right));
    }

     */
    //记忆化递归
    Map<TreeNode, Integer> memo = new HashMap<>();

    public int rob(TreeNode root) {
        if (root == null) return 0;
        return memoDfs(root);
    }

    private int memoDfs(TreeNode root) {
        if (root == null) return 0;
        if (memo.containsKey(root)) return memo.get(root);
        int money = root.val;
        if (root.left != null) {
            money += memoDfs(root.left.left) + memoDfs(root.left.right);
        }
        if (root.right != null) {
            money += memoDfs(root.right.left) + memoDfs(root.right.right);
        }
        int ans = Math.max(money, memoDfs(root.left) + memoDfs(root.right));
        memo.put(root, ans);
        return ans;
    }
}
